package com.jerry.hm.algorithm.recursion;

/**
 * 杨辉三角形
 *
 * @author Jerry
 * @since 2024/10/1 17:53
 */
public class PascalTriangle {

    /**
     * 计算某行某列的值
     *
     * @param i
     * @param j
     * @return
     */
    public static int element(int i, int j) {
        if (j == 0 || i == j) {
            return 1;
        }
        return element(i - 1, j - 1) + element(i - 1, j);
    }

    /**
     * 打印三角形
     *
     * @param n
     */
    public static void print(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-6d", element(i, j));
            }
            System.out.println();
        }
    }

    /**
     * 打印空格
     *
     * @param n 总行数
     * @param i 当前行数
     */
    private static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 3;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    /**
     * 计算某行某列的值-记忆优化版
     *
     * @param i
     * @param j
     * @param cache
     * @return
     */
    public static int element2(int i, int j, int[][] cache) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        if (j == 0 || i == j) {
            cache[i][j] = 1;
            return 1;
        }
        int left = element2(i - 1, j - 1, cache);
        int right = element2(i - 1, j, cache);
        cache[i][j] = left + right;
        return cache[i][j];
    }

    /**
     * 打印三角形-记忆优化版
     *
     * @param n
     */
    public static void print2(int n) {
        int[][] cache = new int[n][];
        for (int i = 0; i < n; i++) {
            cache[i] = new int[i + 1];
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-6d", element2(i, j, cache));
            }
            System.out.println();
        }
    }

    /**
     * 根据缓存创建指定行的缓存
     *
     * @param cache
     * @param row   行号
     */
    private static void createRow(int[] cache, int row) {
        if (row == 0) {
            cache[0] = 1;
            return;
        }
        cache[row - 1] = 1;
        for (int i = row; i > 0; i--) {
            cache[i] = cache[i] + cache[i - 1];
        }
    }

    /**
     * 打印三角形-记忆优化版-一维数组
     *
     * @param n
     */
    public static void print3(int n) {
        int[] cache = new int[n];
        for (int i = 0; i < n; i++) {
            createRow(cache, i);
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-6d", cache[j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        print(10);
        print2(10);
        print3(10);
    }
}
